package org.example.algorithm.binarytree;

import org.example.algorithm.TreeNode;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

public class BuildTreeFromInAndPostOrderSolution {

    public static void main(String[] args) {
        BuildTreeFromInAndPostOrderSolution solution = new BuildTreeFromInAndPostOrderSolution();
        int[] inorder = {9,3,15,20,7};
        int[] postorder = {9,15,7,20,3};
        solution.buildTree2(inorder, postorder);
    }

    //迭代法
    public TreeNode buildTree2(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        TreeNode root = new TreeNode(postorder[postorder.length-1]);
        stack.push(root);
        int index = inorder.length-1;
        for (int i=postorder.length-2;i>=0;i--) {
            TreeNode node = stack.peek();
            if (inorder[index] != node.val) {
                node.right = new TreeNode(postorder[i]);
                stack.push(node.right);
            } else {
                while (!stack.isEmpty() && inorder[index] == stack.peek().val) {
                    node = stack.pop();
                    index--;
                }
                node.left = new TreeNode(postorder[i]);
                stack.push(node.left);
            }
        }
        return root;
    }

    //输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
    //输出：[3,9,20,null,null,15,7]
    //递归
    public TreeNode buildTree(int[] inorder, int[] postorder) {
        if (inorder == null || inorder.length == 0) {
            return null;
        }
        Map<Integer,Integer> posMap = new HashMap<>();
        for (int i=0;i<inorder.length;i++) {
            posMap.put(inorder[i], i);
        }
        return doBuildTree(inorder, postorder, 0, inorder.length-1, 0, postorder.length-1, posMap);
    }

    private TreeNode doBuildTree(int[] inorder, int[] postorder, int inStart, int inEnd, int postStart,
                                 int postEnd, Map<Integer, Integer> posMap){
        if (postStart > postEnd || postStart < 0) {
            return null;
        }
        TreeNode root = new TreeNode(postorder[postEnd]);
        int pos = posMap.get(postorder[postEnd]);
        int rightLen = inEnd - pos;
        root.left = doBuildTree(inorder, postorder, inStart, pos-1, postStart, postEnd-rightLen-1, posMap);
        root.right = doBuildTree(inorder, postorder, pos+1, inEnd, postEnd-rightLen, postEnd-1, posMap);
        return root;
    }
}
